/*
 * @lc app=leetcode.cn id=1011 lang=typescript
 *
 * [1011] 在 D 天内送达包裹的能力
 */

// @lc code=start

//  思想：二分搜索
//  参考：https://labuladong.github.io/algo/2/21/56/

//  复杂度：O(nlogn) O(1)

function shipWithinDays(weights: number[], days: number): number {
    // x: 运载能力，f(x): 运载天数
    const f = (weights: number[], x: number): number => {
        let days = 0
        for (let i = 0; i < weights.length;) {
            let cap = x
            while (i < weights.length) {
                if (cap < weights[i]) break
                else cap -= weights[i]
                i++
            }
            days++
        }
        return days
    }

    let left = Math.max(...weights)  // 最少运最大值
    let right = weights.reduce((prev, curr) => prev + curr) // 最多运总值

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2)
        if (f(weights, mid) <= days) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
};
// @lc code=end

console.log(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  // 15
console.log(shipWithinDays([3, 2, 2, 4, 1, 4], 3))  // 6
console.log(shipWithinDays([1, 2, 3, 1, 1], 4))     // 3
